package edu.cmu.cs211.pg.algorithms;

import java.util.Comparator;
import java.util.Iterator;
import java.util.PriorityQueue;
import java.util.Set;

//import edu.cmu.cs211.pg.algorithms.Dijkstra.WeightedEdgeComparator;
import edu.cmu.cs211.pg.graph.Graph;
import edu.cmu.cs211.pg.graph.MyDirectedGraph;
import edu.cmu.cs211.pg.graph.WeightedEdge;

/**
 * An undirected graph MST interface.
 * 
 * V and E are the vertex and edge types for the graph that we will be searching.
 * That is, this function returns a graph (Graph<V,E>), and takes a graph.
 */
public class Kruskal 
{
	//private UnionFind uf;
    /**
     * Returns a minimum spanning tree of g.
     * 
     * Note: You should only add the edges in one direction.  
     * (Make sure the graph you return has the property |V|=|E|+1)
     * 
     * @param g The graph of which to get the minimum spanning tree
     * 
     * @throws NullPointerException if g is null
     * 
     * @return A graph that is an MST of g or null if no MST exists
     */
	
	/*
	 * create a forest F where each vertex in the graph is a separate tree
	 * create a set S containing all of the edges in the graph
	 * while S is nonempty
	 * remove an edge with minimum weight from S
	 * if that edge connects two different trees, then add it to F to make a single tree
	 * otherwise discard the edge
	 */
	public <V extends Comparable<V>,E extends WeightedEdge<V>> Graph<V,E> spanningTree(Graph<V,E> g) 
	{
		/*
		 * check for null graph
		 */
		if(g==null)
			throw new NullPointerException();
		
		/*
		 * call a new instance of union find and initialize necessary data structures
		 */
		UnionFind<V> uf=new UnionFind<V>();
		PriorityQueue<WeightedEdge<V>> q=new PriorityQueue<WeightedEdge<V>>(1, new WeightedEdgeComparator());
		Set<V> set=g.vertices();
		int numvert=set.size();
		Iterator<V> itr=set.iterator();
		Graph<V, E> toRet=new MyDirectedGraph<V, E>();
		//check to see if graph is just one node, then return that one node.
		
		/*
		 * go through all of the nodes in the graph and add the edges to a priorityqueue
		 */
		while(itr.hasNext()){
			V v=itr.next();
			toRet.addVertex(v);
			Iterator<WeightedEdge<V>> itr2=(Iterator<WeightedEdge<V>>)g.outgoingEdges(v).iterator();
			while(itr2.hasNext()){
				q.add(itr2.next());
			}
		}
		
		/*
		 * union edges here
		 */
		int i=0;
		while((i<numvert-1) && !q.isEmpty()){
			WeightedEdge<V> temp=q.poll();
			if(temp==null)
				throw new NullPointerException();
			if(!uf.find(temp.src()).equals(uf.find(temp.dest()))){ //they are not yet joined
			    uf.union(temp.src(), temp.dest());
			    toRet.addEdge((E)temp);
			    i++;
			}		
		}
		if(i==numvert-1){ 
			return toRet;
		}
		
		return null;
	}
	
	public int compareTo(int i, int j) {
		if(i < j) return -1;
		else if (i > j) return 1;
		else return 0;
	}

	class WeightedEdgeComparator<E> implements Comparator<E> {

		public int compare(E o1, E o2) {
			if ((((WeightedEdge)o1).weight() < (((WeightedEdge)o2).weight()))) return -1;
			else if ((((WeightedEdge) o1).weight()) > (((WeightedEdge)o2).weight())) return 1;
			else return 0;
		}

	}
}
